#define  _CRT_SECURE_NO_WARNINGS
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 // class Solution {
 //     ListNode* bfs(ListNode* head, ListNode* tail)
 //     {
 //         if(!head) return nullptr;
 //         ListNode* next = head->next;
 //         head->next = tail;
 //         return next ? bfs(next, head) : head;
 //     }
 // public:
 //     ListNode* reverseList(ListNode* head) {
 //         return bfs(head, nullptr);
 //     }
 // };
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode* Next = head->next;
        ListNode* ret = reverseList(Next);
        head->next = nullptr;
        Next->next = head;
        return ret;
    }
};